#include <iostream>
#include <string>
#include <iomanip>
#include <fstream>
#include <limits>


using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;

// 图书信息结构体
struct Book {
	string id;	  // ISBN
	string name;  // 书名
	double price; // 定价
};
typedef Book ElemType;

// 链表节点结构体
struct LNode {
	ElemType data; // 数据域
	LNode *next;   // 指针域
};
typedef LNode *LinkList;

// 算法2.6 单链表的初始化
Status InitList_L(LinkList &L) {
	// 构造一个空的单链表L
	L = new LNode;	// 生成新结点作为头结点，用头指针L指向头结点
	L->next = NULL; // 头结点的指针域置空
	L->data.price = 0; // 使用头结点的price字段存储链表长度
	return OK;
}

//销毁
Status DestroyList_L(LinkList &L) {
	LinkList p;
	while (L) {
		p = L;
		L = L->next;
		delete p;
	}
	return OK;
}


Status ClearList(LinkList & L) {
	// 将L重置为空表
	LinkList p, q;
	p = L->next; //p指向第一个结点
	while (p) {    //没到表尾
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL; //头结点指针域为空
	L->data.price = 0;
	return OK;
}

//求表长
int  ListLength_L(LinkList L) {
//返回L中数据元素个数
	LinkList p;
	p = L->next; //p指向第一个结点
	int i = 0;
	while (p) { //遍历单链表,统计结点数
		i++;
		p = p->next;
	}
	return i;
}

//判断表是否为空
int ListEmpty(LinkList L) {
	//若L为空表，则返回1，否则返回0
	if (L->next)  //非空
		return 0;
	else
		return 1;
}

// 算法2.7 单链表的取值
Status GetElem_L(LinkList L, int i, ElemType &e) {
	LNode *p = L->next;
	int j = 1;
	while (p && j < i) {
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;
	e = p->data;
	return OK;
}

// 算法2.8 按值查找
LNode *LocateElem_L(LinkList L, double price) {
	LNode *p = L->next;
	while (p && p->data.price != price) {
		p = p->next;
	}
	return p;
}

// 算法2.9 单链表的插入
Status ListInsert_L(LinkList &L, int i, ElemType &e) {
	LNode *p = L;
	int j = 0;
	while (p && j < i - 1) {
		p = p->next;
		++j;
	}
	if (!p || j > i - 1)
		return ERROR;
	LNode *s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	L->data.price++; // 增加链表长度
	return OK;
}

// 算法2.10 单链表的删除
Status ListDelete_L(LinkList &L, int i) {
	LNode *p = L;
	int j = 0;
	while (p->next && j < i - 1) {
		p = p->next;
		++j;
	}
	if (!(p->next) || j > i - 1)
		return ERROR;
	LNode *q = p->next;
	p->next = q->next;
	delete q;
	L->data.price--; // 减少链表长度
	return OK;
}

// 算法2.11 前插法创建单链表
void CreateList_F(LinkList &L) {
	L = new LNode;
	L->next = NULL;
	L->data.price = 0; // 初始化链表长度为0

	ifstream file("book.txt");
	if (!file) {
		cout << "未找到相关文件，无法打开！" << endl;
		exit(ERROR);
	}

	string head_1, head_2, head_3;
	file >> head_1 >> head_2 >> head_3;

	while (file.good()) {
		LNode *p = new LNode;
		file >> p->data.id >> p->data.name >> p->data.price;
		p->next = L->next;
		L->next = p;
		L->data.price++; // 增加链表长度
	}
	file.close();
}

// 算法2.12 后插法创建单链表
void CreateList_L(LinkList &L) {
	L = new LNode;
	L->next = NULL;
	L->data.price = 0; // 初始化链表长度为0
	LNode *r = L;

	ifstream file("book.txt");
	if (!file) {
		cout << "未找到相关文件，无法打开！" << endl;
		exit(ERROR);
	}

	string head_1, head_2, head_3;
	file >> head_1 >> head_2 >> head_3;

	while (file.good()) {
		LNode *p = new LNode;
		file >> p->data.id >> p->data.name >> p->data.price;
		p->next = NULL;
		r->next = p;
		r = p;
		L->data.price++; // 增加链表长度
	}
	file.close();
}

// 函数声明
void testInitList();
void testDestroyList();
void testClearList();
void testListEmpty();
void testListLength();
void testGetElem();
void testLocateElem();
void testListInsert();
void testListDelete();
void testPrintList();
void testCreateList_F();
void testCreateList_L();

LinkList L;
int main() {
	int choice;
	do {
		cout << "\n单链表操作菜单：" << endl;
		cout << "1. 初始化链表" << endl;
		cout << "2. 销毁链表" << endl;
		cout << "3. 清空链表" << endl;
		cout << "4. 判断链表是否为空" << endl;
		cout << "5. 获取链表长度" << endl;
		cout << "6. 获取指定位置元素" << endl;
		cout << "7. 按值查找元素" << endl;
		cout << "8. 插入元素" << endl;
		cout << "9. 删除元素" << endl;
		cout << "10. 打印链表" << endl;
		cout << "11. 前插法创建链表" << endl;
		cout << "12. 后插法创建链表" << endl;
		cout << "0. 退出" << endl;
		cout << "请选择操作 (0-12): ";
		cin >> choice;

		switch (choice) {
			case 1:
				testInitList();
				break;
			case 2:
				testDestroyList();
				break;
			case 3:
				testClearList();
				break;
			case 4:
				testListEmpty();
				break;
			case 5:
				testListLength();
				break;
			case 6:
				testGetElem();
				break;
			case 7:
				testLocateElem();
				break;
			case 8:
				testListInsert();
				break;
			case 9:
				testListDelete();
				break;
			case 10:
				testPrintList();
				break;
			case 11:
				testCreateList_F();
				break;
			case 12:
				testCreateList_L();
				break;
			case 0:
				cout << "程序退出" << endl;
				break;
			default:
				cout << "无效选择，请重新输入" << endl;
		}

		cin.clear();
		cin.ignore(numeric_limits<streamsize>::max(), '\n');
	} while (choice != 0);

	return 0;
}

// 测试函数实现
void testInitList() {
	if (InitList_L(L) == OK) {
		cout << "链表初始化成功" << endl;
	} else {
		cout << "链表初始化失败" << endl;
	}
}

void testDestroyList() {
	if (DestroyList_L(L) == OK) {
		cout << "链表销毁成功" << endl;
	} else {
		cout << "链表销毁失败" << endl;
	}
}

void testClearList() {
	if (ClearList(L) == OK) {
		cout << "链表清空成功" << endl;
	} else {
		cout << "链表清空失败" << endl;
	}
}

void testListEmpty() {
	if (ListEmpty(L)) {
		cout << "链表为空" << endl;
	} else {
		cout << "链表不为空" << endl;
	}
}

void testListLength() {
	cout << "链表长度为: " << ListLength_L(L) << endl;
}

void testGetElem() {
	int position;
	ElemType e;
	cout << "请输入要获取的元素位置: ";
	cin >> position;
	if (GetElem_L(L, position, e) == OK) {
		cout << "获取成功，元素为: " << e.id << " " << e.name << " " << e.price << endl;
	} else {
		cout << "获取失败" << endl;
	}
}

void testLocateElem() {
	double price;
	cout << "请输入要查找的图书价格: ";
	cin >> price;
	LNode *result = LocateElem_L(L, price);
	if (result) {
		cout << "找到价格为" << price << "的图书：" << result->data.name << endl;
	} else {
		cout << "未找到价格为" << price << "的图书" << endl;
	}
}

void testListInsert() {
	int position;
	ElemType e;
	cout << "请输入要插入的位置: ";
	cin >> position;
	cout << "请输入图书信息 (ISBN 书名 价格): ";
	cin >> e.id >> e.name >> e.price;
	if (ListInsert_L(L, position, e) == OK) {
		cout << "插入成功" << endl;
	} else {
		cout << "插入失败" << endl;
	}
}

void testListDelete() {
	int position;
	cout << "请输入要删除的元素位置: ";
	cin >> position;
	if (ListDelete_L(L, position) == OK) {
		cout << "删除成功" << endl;
	} else {
		cout << "删除失败" << endl;
	}
}

void testPrintList() {
	cout << "当前链表内容：" << endl;
	for (LNode *p = L->next; p; p = p->next) {
		cout << p->data.id << " " << p->data.name << " " << p->data.price << endl;
	}
}

void testCreateList_F() {
	CreateList_F(L);
	cout << "前插法创建链表成功，链表内容：" << endl;
	for (LNode *p = L->next; p; p = p->next) {
		cout << p->data.id << " " << p->data.name << " " << p->data.price << endl;
	}
}

void testCreateList_L() {
	CreateList_L(L);
	cout << "后插法创建链表成功，链表内容：" << endl;
	for (LNode *p = L->next; p; p = p->next) {
		cout << p->data.id << " " << p->data.name << " " << p->data.price << endl;
	}
}
